package com.lry.basic.algorithm.dp;

import java.util.Arrays;

public class BagV2 {

    static int n=4;//物品数量
    static int w[]=new int[]{1,1,2,3};//重量
    static int v[]=new int[]{1,2,3,4};//价值
    static int W=5;//背包承重

    public static void main(String[] args) {
//        System.out.println(new BagV2().bag(new int[]{1,1,2,3},new int[]{1,2,3,4},5));
//        System.out.println(new BagV2().rec(n, W));
//        System.out.println(new BagV2().rec1(0, W));
//        System.out.println(new BagV2().rec3(0, W));
//        System.out.println(new BagV2().bag());
//        System.out.println(new BagV2().bag2());
    }

    /**
     * 返回背包可以装的最大价值
     */
    public int bag(){
        //从前i个物品选择重量不超过j的物品的最大价值
        int[][] dp = new int[n+1][W+1];

        for(int i=0;i<n;i++){
            for(int j=1;j<=W;j++){

                if(j<w[i]){
                    dp[i+1][j] = dp[i][j];
                }else{
                    dp[i+1][j] = Math.max(dp[i][j],dp[i][j-w[i]]+v[i]);
                }

            }
        }
        return dp[n][W];
    }



    //前i个物品挑选总重量不超过j的物品的最大价值
    public int rec(int i,int j){
        if(i==0){
            //没有物品可以挑选了
            return 0;
        }else if(j<w[i-1]){
            //不可以挑选当前物品
            return rec(i-1,j);
        }else{
            //挑选和不挑选都尝试一下
            return Math.max(rec(i-1,j),rec(i-1,j-w[i-1])+v[i-1]);
        }
    }

    int[][] memo = new int[n+1][W+1];
    //从第i个物品挑选总重量不超过j的物品的最大价值
    public int rec1(int i,int j){
        if(memo[i][j]>0){
            return memo[i][j];
        }
        int ans = 0;
        if(i==n){
            //没有物品可以挑选了
            ans = 0;
        }else if(j<w[i]){
            //不可以挑选当前物品
            ans = rec1(i+1,j);
        }else{
            //挑选和不挑选都尝试一下
            ans = Math.max(rec1(i+1,j),rec1(i+1,j-w[i])+v[i]);
        }
        return memo[i][j] = ans;
    }

    public int rec2(int i,int j){
        if(i==n){
            return 0;
        }else if(j<w[i]){
            return rec2(i+1,j);
        }else{
            return Math.max(rec2(i+1,j),rec2(i+1,j-w[i])+v[i]);
        }
    }

    /**
     * 返回最大价值
     * @param i 从第i件物品开始挑选，从0开始
     * @param j 背包剩余承重
     * @return
     */
    public int rec3(int i,int j){
        if(i==n){
            return 0;
        }else if(j<w[i]){
            return rec3(i+1,j);
        }else{
            return Math.max(rec3(i+1,j),rec3(i+1,j-w[i])+v[i]);
        }
    }

    public int bag2(){
        //dp[i][j] 表示从前i件物品挑选重量不超过j所产生的最大价值
        int[][] dp = new int[n+1][W+1];

        for(int i=0;i<n;i++){
            for(int j=1;j<=W;j++){
                if(j<w[i]){
                    dp[i+1][j] = dp[i][j];
                }else{
                    dp[i+1][j] = Math.max(dp[i][j],dp[i][j-w[i]]+v[i]);
                }
            }
        }
        return dp[n][W];
    }

}
